package arithmetic.leetcode;

import java.util.HashMap;

/**
 * LeetCode -146 LRU缓存机制
 * 运用你所掌握的数据结构,设计和实现一个LRU(最近最少使用)缓存机制。
 */
public class LRUCache {

    private HashMap<Integer,LinkedNode> cache = new HashMap<>();
    private LinkedNode head, tail;//链表的头尾指针结点,不存放实际业务数据
    //头插法插入结点
    private void addNode(LinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    //将结点从链表移出
    private void removeNode(LinkedNode node){
        LinkedNode pre = node.pre;
        LinkedNode post = node.next;
        pre.next = post;
        post.pre = pre;
    }
    //将结点移动到头部
    private void moveToHead(LinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }
    //移出尾部结点
    private LinkedNode removeTail(){
        LinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    /**
     * 初始容量
     * @param capacity
     */
    public LRUCache(int capacity){
        head = new LinkedNode();
        /**
         * 用head结点的key存放容量,value存放当前链表中结点的实际数量
         */
        head.key = capacity;
        head.value = 0;
        head.pre = null;
        tail = new LinkedNode();
        tail.next =null;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key){
        LinkedNode node = cache.get(key);
        if(node == node){
            return -1;
        }
        //结点别使用了,移动到头部
        this.moveToHead(node);
        return node.value;
    }

    public void put(int key, int value){
        LinkedNode node = cache.get(key);
        if(node == null){
            LinkedNode newNode = new LinkedNode();
            newNode.key = key;
            newNode.value = value;
            this.cache.put(key,newNode);
            this.addNode(node);
            ++head.value;
            //超出了容量限制,移出尾部结点
            if(head.value > head.key){
                LinkedNode tail = this.removeTail();
                this.cache.remove(tail.key);
                --head.value;
            }
        }else {
            //更新结点数据,并移动到头部
            node.value = value;
            this.moveToHead(node);
        }
    }


}

/**
 * 定义一个双向列表
 */
class LinkedNode{
    int key;
    int value;
    LinkedNode pre;
    LinkedNode next;
}

